#include<vector>
#include<algorithm>
#include <climits>
class Solution {
    const  int max = 50001;
    std::vector<int> help = std::vector<int>(max);
public:
    std::vector<int> sortArray(std::vector<int>& nums) {
        sort2(nums, 0, nums.size() - 1);
        return nums;
    }
    void sort1(std::vector<int>& nums, int l, int r) {
        if (l == r) return;
        sort1(nums, l, (l + r) / 2);
        sort1(nums, (l + r) / 2 + 1, r);
        merge(nums, l, r, (l + r) / 2);
    }
    void sort2(std::vector<int>& nums, int l, int r) {
        int n = nums.size();
        for (int step = 1;step < n;step <<= 1) {
            for (int i = 0;i+step < n;i += step*2) {
                int a = i;
                int b = std::min(i + step * 2-1, n-1);
                merge(nums, a, b,  a+step-1);
            }
        }
    }
    void merge(std::vector<int>& nums, int l, int r, int m) {
        int a = l;
        int b = m+1;
        int s = l;
        int start = l;
        while (a <=m && b <=r) {
            help[s++] = nums[a] < nums[b] ? nums[a++] : nums[b++];
        }
        while (a <= m) {
            help[s++] = nums[a++];
        }
        while (b <= r) {
            help[s++] = nums[b++];
        }
        while (start <= r) {
            nums[start] = help[start];
            start++;
        }
    }
};

